package niuke.week4;

import java.util.Scanner;

/**
 设计LRU缓存结构，该结构在构造时确定大小，假设大小为K，并有如下两个功能
 set(key, value)：将记录(key, value)插入该结构
 get(key)：返回key对应的value值
 [要求]
 set和get方法的时间复杂度为O(1)
 某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的。
 当缓存的大小超过K时，移除最不经常使用的记录，即set或get最久远的。

 */
public class LRU01 {

    static class Node{
        Node next;
        Node pre;
        int value;
        int key;

        public Node(int key,int  value) {
            this.value = value;
            this.key = key;
        }

        public Node() {
        }
    }


    Node head;
    Node tail;

    int count;
    int cap;

    public int getCount() {
        return count;
    }


    public  void print(){
        Node curNode =tail;
        while (curNode!=null) {
            System.out.print(curNode.key + "-->");
            curNode = curNode.next;
        }
        System.out.println();
    }
    public LRU01(int cap) {
        this.cap = cap;
        Node node = new Node();
        this.head = node;
        this.tail = node;
    }


    public  void set(int k,int v){
        //添加新元素
        Node curNode = this.head;
        if(curNode.key == k)//是当前第一个元素，不用管了
            return;
        Node node = new Node(k,v);
        node.pre = curNode;
        curNode.next = node;
        this.head = node;
        this.count++;
        if(count==1){//进来第一个元素就要修改head和tail了
            tail = tail.next;
            tail.pre = null;
        }

        //删除原来的元素
        while (curNode!=null && curNode.key!=k){
            curNode = curNode.pre ;
        }
        if(curNode==null) {//不用删除，没有这个元素
            if(count>this.cap) {//淘汰最后一个
                blance();
            }
            return;
        }

        if(curNode.pre!=null) {  //A--cur--B--C---D
            curNode.pre.next = curNode.next;//A-->B
            curNode.next.pre = curNode.pre;//A<--B

            curNode.next=null;
            curNode.pre=null;
            this.count--;
        }else {//cur--B--C---D
            tail = curNode.next;
            curNode.next.pre=null;
            curNode.next=null;
            this.count--;
        }
        if(count>this.cap) {//淘汰最后一个
             blance();
        }
    }
    public void blance(){
//            System.out.println("-----------------");
            Node tailNext = this.tail.next;
            this.tail.next.pre = null;
            this.tail.next = null;
            this.tail = tailNext;
            count--;
    }

    public  int  get(int k){
        //添加新元素
        Node curNode = this.head;
        if(curNode.key == k)//是当前第一个元素，不用管了
            return curNode.value;

        //删除原来的元素
        while (curNode!=null && curNode.key!=k){
            curNode = curNode.pre ;
        }
        if(curNode==null)//没有这个元素
            return -1;

        if(curNode.pre!=null) {  //A--cur--B--C---D
            curNode.pre.next = curNode.next;//A-->B
            curNode.next.pre = curNode.pre;//A<--B


            head.next = curNode;  //head-->cur
            curNode.pre = head;  //head<--cur
            curNode.next = null;//cur-->null
            head = curNode;
        }else {//cur--B--C---D
            tail = curNode.next;
            curNode.next.pre=null; //  null<--B
            curNode.next=null;// cur--->null

            head.next = curNode;//head-->cur
            curNode.pre = head;//head<--cur
            head = curNode;
        }
        return  curNode.value;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int op = sc.nextInt();
        int cap = sc.nextInt();

        LRU01 lru = new LRU01(cap);
        for (int i = 0; i < op; i++) {
            int opt = sc.nextInt();
            if(opt==1){
                lru.set(sc.nextInt(),sc.nextInt());
            }else{
                int res = lru.get(sc.nextInt());
                System.out.println(res);
            }
//            lru.print();
        }
    }
}